It is well known that several relatively slow processors executing respective multiple tasks in parallel may perform more efficiently than one relatively fast processor executing the same tasks serially. However, the performance gained by using multiple processors depends both on how many processors are used and on the manner in which they are coupled.
One method of coupling processors is to have them operate under control of a single operating system, sharing a byte addressable main memory. A system having this architecture is commonly referred to as a tightly coupled system. Tightly coupled architectures appear to be limited to a maximum configuration of approximately eight processors due to physical limitations such as packaging constraints, as well as limitations inherent to the architecture such as cache coherency and contention in critical sections of the operating system.
A closely coupled architecture avoids many of these problems. In a closely coupled system, multiple data processing systems, each under the control of its own operating system, are joined by a communications network and have direct access to common resources such as a memory module or disk drive. Closely coupled systems are distinguished from loosely coupled systems. The processors in a loosely coupled system generally do not have direct access to a common resource. In a closely coupled system, access to the common resources is coordinated by a set of protocols which are implemented in each of the respective systems software.
Closely coupled systems have several advantages over tightly coupled systems. For example, system structure does not change when a new processor or common resource is added, load balancing and database design are simplified since individual tasks or transactions can be run on any of the coupled processing systems, and the failure of an individual processing system does not necessarily lead to a loss of access to the data. Exemplary closely coupled systems are described in a paper by J. P. Strickland et al. entitled "IMS/VS: An Evolving System", IBM Systems Journal. Vol 21, No. 4, 1982 PP 490-510 and in a paper by N. P. Kronenberg et al. entitled "VAXclusters: a Closely-Coupled Distributed System", ACM Trans. on Computer Systems. Vol. 4, No. 2, May, 1986, PP 130-146.
There are, however, disadvantages to using a closely coupled computer system for resource sharing. One disadvantage relates to interprocess communication, that is, when a first task, running on one processor needs to communicate with a second task, running on another processor. This may occur when the first task wants to access common data that is currently being manipulated by the second task. For example, in a banking system, the first task may be a customer withdrawing money from his account using an automatic teller machine and the second task may be the bank updating his account to process a check. If these tasks are not synchronized, the resulting account balance may be incorrect.
One method of synchronizing tasks in a data sharing environment is known as locking. By this method, a task first obtains access to a data structure known as a lock and then indicates the type of access that is desired in order to either read or modify data in the database that is protected by the lock. Other tasks are prevented from accessing the protected data until the one task changes the indication of the type of access desired and releases the lock so that the other tasks may access it.
In closely coupled multiprocessor data sharing systems, a global lock manager is provided to resolve lock requests among tasks running on different processors and to maintain queues of tasks awaiting access to particular lock entities. A global lock manager of this type typically relies on synchronous inter-processor communication to manage the lock entities. That is to say, a first task requesting a lock entity may interrupt second task running on a different processor and hold the second task interrupted until the availability of the lock entity is resolved. This synchronous inter-processor communication increases the response time of the both tasks, causing an apparent increase in the utilization of system resources such as memory, address spaces and locks. This, in turn, tends to increase inter-task contention for these resources, resulting in an increased need for inter-processor communication.
To solve this problem, the requesting task may be suspended if the global lock manager needs to communicate with another processor to resolve the lock request. However, this entails a rescheduling penalty for the suspended task and results in elongation of transaction response and resource holding times.
From the above, it can be understood that inter-processor communication overhead is a key source of performance degradation in a closely coupled data sharing architecture. The inventors have determined that the process of obtaining and releasing a lock may add on the order of several hundred instructions while the overhead for an inter-processor communication operation may be as high as several thousands of instructions. Any locking method which could reduce this overhead would necessarily increase the performance of the shared-data system.
There are many ways to approach global lock management. One method is to distribute the locking function among the coupled processors. By this method, an attempt is made to resolve the lock requests from within the processor. Whenever this is not possible, communication with a remote processor is initiated to resolve the lock request. Distributed locking protocols generally divide the lock space into multiple partitions which are assigned to respective ones of the coupled processors. Requests for an entity (i.e. a particular lock data structure) are sent to, and resolved by the processor which owns the partition to which the entity belongs.
The lock space may be partitioned statically or dynamically. In a static lock partitioning scheme, the assignment of entities to processors is fixed. In dynamic partitioning schemes, the processor which is executing a task that first requests a particular lock entity, is assigned the partition to which the entity belongs. Subsequent requests for entities in this partition are resolved by this processor until no lock entities in the partition are held by the owning processor. In this instance, the processor releases ownership of the partition, which is then acquired by the next processor that requests a lock in the partition.
This dynamic partitioning scheme exploits a locality property which is commonly found in data base or file access program suites. According to this property, during any relatively short time interval, tasks tend to request lock entities that protect a related set of data records. Consequently, if these lock entities may be assigned to the same partition, the dynamic partitioning can reduce the probability of sending a lock request from one processor to another.
However, in environments where there is a high degree of multiprogramming or in systems including a relatively large number of coupled processors, it is likely that two consecutive requests for entities in one partition may originate from different processors. This problem may be resolved by increasing the number of classes but doing so adversely affects the locality behavior.
The paper by Strickland et al., referred to above, describes a locking protocol in which one global locking table is continuously circulated among the coupled processors. A request for a lock is granted only when all of the processors agree to the request. This scheme results in a relatively large inter-processor communication delay since each processor is interrupted to examine the request and convey the table to the next processor.
U.S. Pat. No. 4,224,664 to Trinchieri relates to a method for concurrency control which is known in the literature as serialization graph checking. By this method, two memories are accessed to grant or deny a request for a lock entity. The first memory holds a utilization graph that identifies which processes access which data items. The second memory contains a serialization graph that identifies precedence relationships among the processes (i.e. that one process must occur in time before the other process). This graph is used to deny the lock if granting it would result in a deadlock condition or in a situation in which two tasks would need precedence over each other.